<html>
  <head>
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
    <title>dsearch</title>
  </head>
  <body bgcolor="#FFFFFF">
    <center>Scilab Function</center>
    <div align="right">Last update : 11/03/2005</div>
    <p>
      <b>dsearch</b> - binary search (aka dichotomous search in french)</p>
    <h3>
      <font color="blue">Calling Sequence</font>
    </h3>
    <dl>
      <dd>
        <tt>[ind, occ, info]  = dsearch(X, val [, ch ])  </tt>
      </dd>
    </dl>
    <h3>
      <font color="blue">Parameters</font>
    </h3>
    <ul>
      <li>
        <tt>
          <b>X</b>
        </tt>: a real vector or matrix</li>
      <li>
        <tt>
          <b>val</b>
        </tt>: a real (row or column) vector with n components in strictly increasing 
             order val(1) &lt; val(2) &lt; ... &lt; val(n)</li>
      <li>
        <tt>
          <b>ch</b>
        </tt>: (optional) a character "c" or "d" (default value "c")</li>
      <li>
        <tt>
          <b>ind</b>
        </tt>: a real vector or matrix with the same dimensions than X</li>
      <li>
        <tt>
          <b>occ</b>
        </tt>: a real vector with the same format than val (but with n-1 components in the case ch="c")</li>
      <li>
        <tt>
          <b>info</b>
        </tt>: integer</li>
    </ul>
    <h3>
      <font color="blue">Description</font>
    </h3>
    <p>This function is useful to search in an ordered table and/or to count the number of components
       of a vector falling in some classes (a class being an interval or a value).
    </p>
    <p>By default or when <tt>
        <b>ch="c"</b>
      </tt>, this is the interval case, that is, for 
       each X(i) search in which of the n-1 intervals it falls, the intervals being defined by:
    </p>
    <pre>
            I1 = [val(1), val(2)]
            Ik = (val(k), val(k+1)] for 1 &lt; k &lt;= n-1 ; 
</pre>
    <p>and:
    </p>
    <dd>
      <li>
        <b>
          <font color="maroon">ind(i)</font>
        </b>: is the interval number of X(i) (0 if X(i) is not in
              [val(1),val(n)])</li>
      <li>
        <b>
          <font color="maroon">occ(k)</font>
        </b>: is the number of components of X which are in Ik</li>
      <li>
        <b>
          <font color="maroon">info</font>
        </b>: is the number of components of X which are not in [val(1),val(n)]</li>
    </dd>
    <p>When <tt>
        <b>ch="d"</b>
      </tt> case, this is the discrete case, that is, for 
       each X(i)  search if it is equal to one val(k) and:
    </p>
    <dd>
      <li>
        <b>
          <font color="maroon">ind(i)</font>
        </b>: is equal to the index of the component of val which matches X(i) 
               (ind(i) = k if X(i)=val(k)) or 0 if X(i) is not in val.</li>
      <li>
        <b>
          <font color="maroon">occ(k)</font>
        </b>: is the number of components of X equal to val(k)</li>
      <li>
        <b>
          <font color="maroon">info</font>
        </b>: is the number of components of X which are not in the set {val(1),...,val(n)}</li>
    </dd>
    <h3>
      <font color="blue">Examples</font>
    </h3>
    <pre>

// example #1 (elementary stat for U(0,1))
m = 50000 ; n = 10;
X = grand(m,1,"def");
val = linspace(0,1,n+1)';
[ind, occ] = dsearch(X, val);
xbasc() ; plot2d2(val, [occ/m;0])  // no normalisation : y must be near 1/n


// example #2 (elementary stat for B(N,p))
N = 8 ; p = 0.5; m = 50000;
X = grand(m,1,"bin",N,p); val = (0:N)';
[ind, occ] = dsearch(X, val, "d");
Pexp = occ/m; Pexa = binomial(p,N); 
xbasc() ; hm = 1.1*max(max(Pexa),max(Pexp));
plot2d3([val val+0.1], [Pexa' Pexp],[1 2],"111",  ...
        "Pexact@Pexp", [-1 0 N+1 hm],[0 N+2 0 6])
xtitle(  "binomial distribution B("+string(N)+","+string(p)+") :" ...
        +" exact probability versus experimental ones")


// example #3 (piecewise Hermite polynomial)
x = [0 ; 0.2 ; 0.35 ; 0.5 ; 0.65 ; 0.8 ;  1];
y = [0 ; 0.1 ;-0.1  ; 0   ; 0.4  ;-0.1 ;  0];
d = [1 ; 0   ; 0    ; 1   ; 0    ; 0   ; -1];
X = linspace(0, 1, 200)';
ind = dsearch(X, x);
// define Hermite base functions
deff("y=Ll(t,k,x)","y=(t-x(k+1))./(x(k)-x(k+1))")   // Lagrange left on Ik
deff("y=Lr(t,k,x)","y=(t-x(k))./(x(k+1)-x(k))")     // Lagrange right on Ik
deff("y=Hl(t,k,x)","y=(1-2*(t-x(k))./(x(k)-x(k+1))).*Ll(t,k,x).^2")
deff("y=Hr(t,k,x)","y=(1-2*(t-x(k+1))./(x(k+1)-x(k))).*Lr(t,k,x).^2")
deff("y=Kl(t,k,x)","y=(t-x(k)).*Ll(t,k,x).^2")
deff("y=Kr(t,k,x)","y=(t-x(k+1)).*Lr(t,k,x).^2")
// plot the curve
Y = y(ind).*Hl(X,ind) + y(ind+1).*Hr(X,ind) + d(ind).*Kl(X,ind) + d(ind+1).*Kr(X,ind);
xbasc(); plot2d(X,Y,2) ; plot2d(x,y,-9,"000") 
xtitle("an Hermite piecewise polynomial")
// NOTE : you can verify by adding these ones : 
// YY = interp(X,x,y,d); plot2d(X,YY,3,"000")
   
  </pre>
    <h3>
      <font color="blue">See Also</font>
    </h3>
    <p>
      <a href="../programming/find.htm">
        <tt>
          <b>find</b>
        </tt>
      </a>,&nbsp;&nbsp;<a href="../statistics/tabul.htm">
        <tt>
          <b>tabul</b>
        </tt>
      </a>,&nbsp;&nbsp;</p>
    <h3>
      <font color="blue">Author</font>
    </h3>
    <p>B.P.   </p>
  </body>
</html>
